package demo.practice.dp;

public class P516 {

    public static void main(String[] args) {
        P516 p516= new P516();
        p516.longestPalindromeSubseq("bbbab");
    }
    /**
     * 最大回文子序列
     *
     * @param s
     * @return
     */
    public int longestPalindromeSubseq(String s) {
        if (s == null) {
            return 0;
        }
        int len = s.length();
        char[] cs = s.toCharArray();
        //状态转义方程式  当cs[i]==cs[j]
        // 则有dp[i][j]= dp[i+1][j-1]。
        // 否则dp[i][j] = Max(dp[i+1][j],dp[i][j-1])
        int[][] dp = new int[len][len];

        for (int i = len - 1; i >= 0; i--) {
            dp[i][i]=1;
            for (int j = i + 1; j < len; j++) {
                if (cs[i] == cs[j]) {
                    dp[i][j] = dp[i + 1][j - 1]+2;
                } else {
                    dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[0][len - 1];
    }
}
